package algorithm.leecode.permutation;
import java.util.LinkedList;

/**
 * @author bingo
 * @Description 全排列问题
 *              [1,2,3]  给定1,2,3 求出所有可能
 * @Date 2018/9/4
 */
public class Permutations {
    private  boolean[] used ;

    private  int count=0;

    public Permutations(int length) {
        used = new boolean[length];
        for(int i=0;i<length;i++){
          used[i] = false;
        }
    }

    /**
     *       1 2 3
     *
     *
     *
     * **/
    public void generation(int startIndex,int[] digits,LinkedList<Integer> list) {
           // System.out.println("startIndex："+startIndex);
            if (startIndex == digits.length) {
                count++;
                for (Integer item : list) {
                    System.out.print(item);
                }
                System.out.println();
                return;
            }
            //借助其他辅助数据结构
            for (int i = 0; i < digits.length; i++) {
                //判断list中是否已经包含了该元素，可以对list 进行遍历
                if (!used[i]) {
                    used[i] = true;
                    int nextIndex = startIndex + 1;
                    list.addLast(digits[i]);
                    generation(nextIndex, digits, list);
                   // System.out.println("startIndex："+startIndex);
                    list.removeLast();
                    used[i] = false;
                }

            }

   /*     for (int i = 0; i < digits.length; i++) {
            //判断list中是否已经包含了该元素，可以对list 进行遍历
            if (!list.contains(digits[i])) {
                int nextIndex = startIndex + 1;
               list.addLast(digits[i]);
                generation(nextIndex, digits, list);
                list.removeLast();
            }

        }*/

        }
        public static void main(String[] args) {
            int[] digits = new int[]{1,2,3,4,5,6,6};
        Permutations permutations = new Permutations(digits.length);
        permutations.generation(0,digits,new LinkedList<>());
            System.out.println("可能性:"+permutations.count);
    }

    public boolean isExisted(int item,LinkedList list){
        return  list.contains(item);
    }
}
